package leetcode.backtrace;

import java.util.*;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-18 11:29:25
 */


/*
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode126_FindLadders {

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        int[] visited = new int[wordList.size()];
        List<List<String>> result = new ArrayList<>();
        List<String> tempResult = new ArrayList<>();
        Map<String, Integer> distance = new HashMap<>();

        tempResult.add(beginWord);
        findLadders(beginWord, endWord, wordList, result, visited, tempResult, 1, distance);

        return result;
    }

    public void findLadders(String beginWord, String endWord, List<String> wordList, List<List<String>> result, int[] visited, List<String> tempResult, int level, Map<String, Integer> distance) {

        // 剪枝1：大于已有结果层数的递归可以不用再做
        if (result.size() > 0 && result.get(0).size() <= level) return;


        Stack<String> stack = new Stack<>();
        for (int i = 0; i < wordList.size(); i++) {
            if ( visited[i] != 1 && findLadders(beginWord, wordList.get(i)) >= 0){
                stack.add(wordList.get(i));
                visited[i] = 1;
            }
        }

        boolean flag = false;

        while (!stack.isEmpty()){
            String tempS = stack.pop();

            // 剪枝2：重复出现的单词，更大层数的情况不用再递归


            // 剪枝3：该层已有结果，其他不用再递归
            if (!flag){
                if (tempS.equals(endWord)){
                    tempResult.add(tempS);

                    if (distance.containsKey(tempS)){
                        if(distance.get(tempS) < level) {
                            visited[wordList.indexOf(tempS)] = 0;
                            continue;
                        }
                    }
                    distance.put(tempS, level);

                    if (result.size() == 0){
                        result.add(tempResult);
                    }else{
                        if (result.get(0).size() == tempResult.size()){
                            result.add(tempResult);
                        }else if(result.get(0).size() > tempResult.size()){
                            result.clear();
                            result.add(tempResult);
                        }
                    }
                    flag = true;
                }else{
                    List<String> newTempResult = new ArrayList<>(tempResult);
                    newTempResult.add(tempS);



                    findLadders(tempS, endWord, wordList, result, visited, newTempResult, level + 1, distance);
                }
            }
            visited[wordList.indexOf(tempS)] = 0;
        }
    }

    // 时间复杂度 mn
    // hashset + 改变word中的一个字母，然后从列表中找相同word的方式时间复杂度 26n~n
    public int findLadders(String beginWord, String endWord) {

        // if (beginWord.length() != endWord.length()) return;
        int len = 0, count = 0;
        while (len < beginWord.length()){
            if (beginWord.charAt(len) != endWord.charAt(len)){
                count++;
                if (count > 1) return -1;
            }
            len++;
        }
        if (count == 1) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        String beginWord = "qa";
        String endWord = "sq";
        // List<String> wordList = Arrays.asList("hot","dot","dog","lot","cog");
        // List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
        List<String> wordList = Arrays.asList("si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye");

        List<List<String>> ladders = new LeetCode126_FindLadders().findLadders(beginWord, endWord, wordList);

        System.out.println("ladders = " + ladders);
    }


}
